//
// Created by Administrator on 2022/1/7.
//

#ifndef CPP_LEARNING_HEAP_HPP
#define CPP_LEARNING_HEAP_HPP

// i 是一个从零开始的数值
#define Parent(i) ((i-1)>>1)
#define LChild(i)  (1+((i)<<1))   // 奇数
#define RChild(i)  ((1+(i))<<1)   // 偶数
typedef int Rank;
#include <vector>
#include "utils.h"
using namespace std;
template <typename T>
class Heap{

private:
    vector<T> _elem;
protected:
    Rank percolateDown(Rank n, Rank i);              // 下滤
    Rank percolateUp(Rank i);                        // 上滤
    void heapify(Rank n);                            // 建堆

    Heap(T* A, Rank n){
        for(int i=0; i<n; i++){
            _elem.push_back(A[i]);
        }
        heapify(n);
    }

    void insert(T &); // 插入
    T getMax() { return  _elem[0];} //
    T delMax();

};
template <typename T>
void Heap<T>::heapify(Rank n){
    for(int i=_elem.size()-1; i>0; i--){
        percolateDown(_elem.size(), i);
    }
}

template <typename T>
void Heap<T>::insert(T& e){
    _elem.push_back(e);
    percolateUp(_elem.size()-1);
}
template <typename T>
T Heap<T>::delMax(){
    if(_elem.size() == 1){
        T e = _elem.end();
        _elem.pop_back();
        return e;
    }

    myswap(_elem[0],_elem.end());
    T e = _elem.end();
    _elem.pop_back();
    percolateDown(_elem.size(),0);
    return e;
}


template <typename T>
Rank Heap<T>::percolateDown(Rank n, Rank i){
    while (i<n){
        if(LChild(i) < n){

            if(RChild(i) < n){
                Rank max_i = _elem[LChild(i)] < _elem[RChild(i)] ? RChild(i) : LChild(i);
                if(_elem[i] < _elem[max_i]){
                    myswap(_elem[i] , _elem[max_i]);
                    i = max_i;
                }else{
                    break;
                }

            }else{
                if(_elem[i] < _elem[LChild(i)]){
                    myswap(_elem[i] , _elem[LChild(i)]);
                    i = LChild(i);
                } else{
                    break;
                }
            }
        }else{
            break;
        }
    }
}



template <typename T>
Rank Heap<T>::percolateUp(Rank i){
    while (i > 0){
        if(_elem[Parent(i)] < _elem[i]){
            myswap(_elem[i] , _elem[Parent(i)]);
            i = Parent(i);
        }else{
            break;
        }
    }
}



#endif //CPP_LEARNING_HEAP_HPP
